/**
 * Copyright (C) 2025 pony working team
 * SPDX-License-Identifier: MulanPSL-2.0
 */

/* define to prevent recursive inclusion -------------------------------------*/
#ifndef __X_RBTREE_H__
#define __X_RBTREE_H__

/* includes (standard library, system) ---------------------------------------*/
/* includes (other library) --------------------------------------------------*/
/* includes (project) --------------------------------------------------------*/
/* includes (local) ----------------------------------------------------------*/
#include "private/bi_tree.h"

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

/* defines -------------------------------------------------------------------*/

#define RBTREE_RED   0
#define RBTREE_BLACK 1

#define RBTREE_DEBUG

/* typedefs ------------------------------------------------------------------*/

typedef struct rb_node {
    bi_node_t bin;
    int c; /* color */
} rb_node_t;

typedef struct rb_tree {
    bi_tree_t bit;

#ifdef RBTREE_DEBUG
    uint32_t nodes;
#endif
} rb_tree_t;

/* macro ---------------------------------------------------------------------*/
/* inlines -------------------------------------------------------------------*/
/* externs -------------------------------------------------------------------*/

extern int rb_insert(rb_tree_t *t, rb_node_t *n);
extern void rb_delete(rb_tree_t *t, rb_node_t *n);
extern void rb_init(rb_tree_t *t, int (*compare_nn)(bi_node_t *a, bi_node_t *b),
                    int (*compare_nk)(bi_node_t *n, uintptr_t k));
extern rb_node_t *rb_find_eq(rb_tree_t *t, uintptr_t k);
extern rb_node_t *rb_find_ge(rb_tree_t *t, uintptr_t k);
extern rb_node_t *rb_find_gt(rb_tree_t *t, uintptr_t k);
extern rb_node_t *rb_find_le(rb_tree_t *t, uintptr_t k);
extern rb_node_t *rb_find_lt(rb_tree_t *t, uintptr_t k);
extern rb_node_t *rb_first(rb_tree_t *t);
extern rb_node_t *rb_last(rb_tree_t *t);
extern rb_node_t *rb_next(rb_node_t *n);
extern rb_node_t *rb_prev(rb_node_t *n);
extern rb_node_t *rb_node_get(rb_tree_t *t, uintptr_t k,
                              bi_node_t *(*create)(uintptr_t k, uintptr_t arg), uintptr_t arg);
extern void rb_foreach(rb_tree_t *t, int (*pfn)(bi_node_t *));
extern void rb_replace(rb_tree_t *t, rb_node_t *o, rb_node_t *n);

#ifdef __cplusplus
}
#endif /* __cplusplus */

#endif /* __X_RBTREE_H__ */
